Pattern search is a simple yet powerful machine vision tool. Given a template pattern and an image, its objective is to find all instances of the patterns in the image. It involves two steps, a search step and a matching step. The search step places the pattern at all valid poses (locations, rotation angles, sizes) of the image being searched. The matching step determines the goodness of the match between the pattern at a given pose and the subset of the image corresponding to the pose. For advanced applications, it is desirable that the matching step produces high precision (that is, subpixel position, subsampling scale and rotation) results.
Normalized correlation method (Manickam, Swami, Roth, Scott D., Bushman, Thomas, “Intelligent and Optimal Normalized correlation for High-Speed Pattern Matching”, NEPCON WEST 2000, February 2000) of fixed rotation and scale has been widely used as the matching method in many machine vision applications. The match score of normalized correlation is largely independent of linear variations in object shading caused by reflectivity or illumination variations.
A rotation and scale invariant pattern matching method was disclosed (Rotation and Scale Invariant Pattern Matching Method, U.S. Pat. No. 6,640,008) that generates a polar coordinate representation of the pattern template image that allows for fast linear search of scale along the radius axis and rotation along the angular axis. A fast regular shaped pattern search method was disclosed (Fast Regular Shaped Pattern Searching, U.S. patent application Ser. No. 10/255,016) that performs fast pattern matching with flexible projection kernels to construct regular-shaped patterns using an accumulation method. A fast invariant searching method was disclosed (Fast Invariant Pattern Search, U.S. patent application Ser. No. 10/302,466). It generates rotation and scale invariant profiles for fast invariant search using the fast regular shaped pattern construction method. In addition, a fast pattern searching method was disclosed (Fast Pattern Searching, U.S. patent application Ser. No. 10/283,380) that performs fast scale and aspect ratio invariant search.
The above prior art approaches are not designed for highly precise sub-pixel and sub-sampling matching. They return the discrete pixel position that yields the best match and the coarse rotation and scale estimate. A surface fitting approach (Gleason, S. S., M. A. Hunt, and W. B. Jatko, “Subpixel Measurement of Image Features Based on Paraboloid Surface fit”, SPEE Vol. 1386. Machine Vision Systems Integration in Industry, 1990) is attempted for subpixel matching. This approach fits the surface of the template matching scores (such as normalized correlation values) and estimates the maximum position from the surface for subpixel matching results. The fitting method suffers from the underlying nonlinear matching functions whose scores cannot be well characterized by the fitting surfaces. This, therefore, could yield misleading subpixel (for shift) or subsampling (for rotation and/or scale) matching results. It is reported that the error of the template matching score fitting based method is about 13% (Frischchlz Robert W. and Spinnler, Klaus P. “Class of algorithms for real-time subpixel registration” Proc. SPIE Vol. 1989, p. 50-59, Computer Vision for Industry, Donald W. Braggins; Ed).
A more accurate approach is to perform subpixel and subsampling interpolation in the image domain. Then, template matching is performed on the interpolated higher resolution image. This could yield more accurate results than performing interpolation on the matching score surface. Depending on the interpolation method, system noise and the number of bits per pixel used to quantized the data, it is expected that a midrange error of 0.01 to 0.05 pixel could be achieved using this method (Frischchlz Robert W. and Spinnler, Klaus P. “Class of algorithms for real-time subpixel registration” Proc. SPIE Vol. 1989, p. 50-59, Computer Vision for Industry, Donald W. Braggins; Ed). However, interpolation on the image domain for high precision matching requires large data volume and matching computation, which is too expensive for deployment in practical applications.
A prior art approach (“Golden template comparison for rotated and/or scaled images” U.S. Pat. No. 5,850,466) stores, in an array, a varied plurality of golden template images, each golden template image being characterized by a different combination of rotation and/or scale and/or sub-pixel translation. The array is indexed by the respective quantized rotation and/or quantized scale and/or sub-pixel translation of each version of the golden template image. This approach still requires a large number of template storage and computational cost for matching at high precision. So it is still impractical.